/**
 * In the following equation x, y, and n are positive integers.
 *
 *    1/x + 1/y = 1/n
 *
 * For n = 4 there are exactly three distinct solutions:
 *
 *    1/5 + 1/20 = 1/4
 *    1/6 + 1/12 = 1/4
 *    1/8 + 1/8 = 1/4
 *
 * What is the least value of n for which the number of distinct solutions
 * exceeds one-thousand?
 *
 * SOLUTION:
 *
 * We observe the following relationship:
 *
 *   (x-n)*(y-n) = n^2
 *
 * Hence the solutions (x,y) map one-to-one to the divisors of n^2.
 *
 * Let the prime factors of n be (p1,p2,...,pm), then (x,y) is a partition of
 *
 *   (p1^2k1)*(p2^2k2)*...*(pm^2km) = n^2.
 *
 * The detailed solution is presented for problem 110.
 */

#include <iostream>
#include "euler/prime_factor.hpp"
#include "euler.h"

BEGIN_PROBLEM(108, solve_problem_108)
	PROBLEM_TITLE("Solving the Diophantine equation 1/x + 1/y = 1/n")
	PROBLEM_ANSWER("180180")
	PROBLEM_DIFFICULTY(1)
	PROBLEM_FUN_LEVEL(1)
	PROBLEM_TIME_COMPLEXITY("")
	PROBLEM_SPACE_COMPLEXITY("")
END_PROBLEM()

using namespace euler;

static int count_solutions(int n)
{
	int count = 1;
	prime_factorize_distinct(n, [&count](int /* p */, int k) {
		count *= (2 * k + 1);
	});
	return (count + 1) / 2;
}

static void display_prime_factors(int n)
{
	std::cout << "Prime factors of " << n << ":" << std::endl;
	prime_factorize(n, [](int p) {
		std::cout << p << ' ';
	});
	std::cout << std::endl;
}

static void solve_problem_108()
{
	bool verbose = false;
	for (int n = 2; ; n++)
	{
		int count = count_solutions(n);
		if (count >= 1000)
		{
			if (verbose)
			{
				std::cout << "Number of solutions for " << n << " is "
					<< count << std::endl;
				display_prime_factors(n);
			}
			else
			{
				std::cout << n << std::endl;
			}
			break;
		}
	}
}
